package lc20240614;

/**
  * @description N皇后有多少种不同的解法
  * @author 不知名帅哥
  * @date 2024/6/14 23:48
  * @version 1.0
*/
public class NQueen2 {
    private int count=0;
    public int totalNQueens(int n) {
        boolean[] cols = new boolean[n]; // 列是否有皇后
        boolean[] diag1 = new boolean[2 * n]; // 副对角线是否有皇后
        boolean[] diag2 = new boolean[2 * n]; // 主对角线是否有皇后

        backtrack(0, cols, diag1, diag2, n);
        return count;
    }

    private void backtrack(int row, boolean[] cols, boolean[] diag1, boolean[] diag2, int n) {
        if (row == n) {
            count++;
            return;
        }
        for (int col = 0; col < n; col++) {
            int d1 = row - col + n;
            int d2 = row + col;
            if (!cols[col] && !diag1[d1] && !diag2[d2]) {
                cols[col] = true;
                diag1[d1] = true;
                diag2[d2] = true;
                backtrack(row + 1, cols, diag1, diag2, n);
                cols[col] = false;
                diag1[d1] = false;
                diag2[d2] = false;
            }
        }
    }
}
